The present invention relates to a self-routing switch and, more particularly, to a self-routing switch which effects distributed control by hardware and is suitable for use as an interconnection network for multiprocessor communications in a computer or a switch for fast packet switching.
FIG. 1 is a diagram showing an example of a conventional switching circuit (with 16 input lines and 16 output lines) known as a typical self-routing switch (see C. Wu and T. Fung, "Routing techniques for a class of multistage interconnection networks", 1978 Int'l Conf. Parallel Processing, pp. 197-205, for example).
In FIG. 1 reference characters IT.sub.0 to IT.sub.15 indicate input lines, OT.sub.0 to OT.sub.15 output lines, HI.sub.0 to HI.sub.15 routing information inserters, HE.sub.0 to HE.sub.15 routing information eliminators, and E.sub.1,0 to E.sub.4,7 circuits (hereinafter referred to as switching elements) which determine the output line to which information data to be transferred is to be output in accordance with a destination address appended to the information data.
The switching elements E.sub.j,0 to E.sub.j,7 (where j=1 to 4) constitute a jth switching stage ST.sub.j. Reference characters L.sub.1,0 to L.sub.5,15 denote links which interconnect the routing information inserters, the routing information eliminators and the switching elements. Input links to the jth switching stage ST.sub.j are sequentially identified by L.sub.j,0 to L.sub.j,15 from the top. The links from each switching stage to the next one are provided so that any routing information inserter HI can be connected to any routing information eliminator HE.
The routing from each routing information inserter HI to a desired routing information eliminator HE is determined by a destination address contained in routing information appended to information data. The routing information inserter HI inserts routing information into information data which is supplied thereinto from an input line, and the routing information eliminator HE eliminates the routing information from the information data.
The routing information contains the address of a routing information eliminator HE.sub.p which is a specified destination of information data and is represented in a binary form, (d.sub.3, d.sub.2, d.sub.1, d.sub.0), where p=d.sub.3 .multidot.2.sup.3 +d.sub.2 .multidot.2.sup.2 +d.sub.1 .multidot.2.sup.1 +d.sub.0 .multidot.2.sup.0. Consequently, p takes an arbitrary value from 0 to 15 in this instance. It is predetermined, as a promise, that the switching element E.sub.j,i of the jth switching stage ST.sub.j outputs information data to an upper or lower outgoing link depending whether the bit d.sub.4-j in the bit string (d.sub.3, d.sub.2, d.sub.1, d.sub.0) is "0" or "1". In the following description this bit d.sub.4-j may therefore be referred to as judge bit for routing operation by each switching element E.sub.j,i in the jth stage ST.sub.j. After passing through all the switching stages information data reaches the specified routing information eliminator HE.sub.p.
Such a conventional self-routing switch as described above is easy of control, because the routing path is determined uniquely. However, when a link contention by a plurality of information data occurs in the switching network, some of the information data must be abandoned or buffered into a buffer of a limited capacity; consequently, as the scale of the switching network enlarges, the number of information data which can reach the output line side decreases, or a delay time of information data increases. This leads to the defect that the throughput (i.e. the output line utilization factor) of the switching network is very low.
This defect is experienced also in other conventional switching networks which differ from the above-said one in link wiring algorithm alone. There has also been proposed a switching network of the type in which no link contention occurs unless a plurality of information data are directed to the same output trunk (see J. Y. Hui and E. Arthurs, "A broadband packet switch for integrated transport", IEEE J. Select. Areas
Commun., vol. SAC-5, pp. 1264-1273, Oct. 1987, for instance), but a very large number of stages of preceding circuits for avoiding the contention are required.
In U.S. Pat. No. 4,661,947 there is disclosed a self-routing switch in which switching elements in each switching stage are connected in pairs by internal links so that if a link contention occurs between two pieces of information data in one of the switching elements of a certain pair, one of the pieces of information data is transferred to the other switching element for its routing operation. However, this arrangement does not so much improve the overall throughput of the switch either.